// 2015年版权所有etcd作者
// 
// 根据Apache许可证2.0版（以下简称“许可证”）获得许可；
// 除非遵守许可证，否则不得使用此文件。
// 您可以通过
// 
// www.apache.org/licenses/LICENSE-2.0 
// 
// 除非适用法律要求或书面同意，否则根据许可证分发的软件
// 按“原样”分发，
// 无任何明示或暗示的保证或条件。
// 请参阅许可证，了解管理许可的特定语言和
// 许可证下的限制。

package raft

import (
	"errors"
	"sync"

	pb "go.etcd.io/etcd/raft/v3/raftpb"
)

// 由存储返回。Entries/Compact当请求的
// 索引不可用时，因为它早于最后一个快照。
var ErrCompacted = errors.New("requested index is unavailable due to compaction")

// ErrSnapOutOfDate由存储返回。当请求的
// 索引早于现有快照时创建快照。
var ErrSnapOutOfDate = errors.New("requested index is older than the existing snapshot")

// 当请求的日志项
// 不可用时，存储接口返回ErrUnavailable。
var ErrUnavailable = errors.New("requested entry at index is unavailable")

// 当所需的
// 快照暂时不可用时，存储接口返回errSnapshotTemporaryUnavailable。
var ErrSnapshotTemporarilyUnavailable = errors.New("snapshot is temporarily unavailable")

// 存储是一个可由应用程序
// 实现的接口，用于从存储中检索日志条目。
// 
// 如果任何存储方法返回错误，raft实例将
// 不可操作并拒绝参与选举；在这种情况下，应用程序负责清理和恢复。
type Storage interface {
	// TODO（tbg）：将其拆分为两个接口，LogStorage和StateStorage。

	// InitialState返回保存的HardState和ConfState信息。
	InitialState() (pb.HardState, pb.ConfState, error)
	// Entries返回[lo，hi]范围内的一部分日志项。
	// MaxSize限制返回的日志项的总大小，但
	// Entries至少返回一个项（如果有）。
	Entries(lo, hi, maxSize uint64) ([]pb.Entry, error)
	// Term返回条目i的项，该项必须在
	// [FirstIndex（）范围内-1，LastIndex（）].
	// FIRSTDINDEX之前的项的期限将保留以进行匹配，即使该项的其余部分可能不可用。
	Term(i uint64) (uint64, error)
	// LastIndex返回日志中最后一个项的索引。
	LastIndex() (uint64, error)
	// FIRSTDINDEX返回第一个日志项的索引，即
	// 可能通过条目可用（较旧的条目已合并到最新快照中；如果存储仅包含虚拟条目，则第一个日志条目不可用）.
	FirstIndex() (uint64, error)
	// 快照返回最近的快照。
	// 如果快照暂时不可用，它应该返回errSnapshotTemporaryUnavailable，
	// 以便raft状态机可以知道存储需要一些时间来准备
	// 快照并稍后调用快照。
	Snapshot() (pb.Snapshot, error)
}

// 我moryStorage实现由内存阵列中的
// 支持的存储接口。
type MemoryStorage struct {
	// 保护对所有字段的访问。大多数MemoryStorage方法是
	// 在raft goroutine上运行，但Append（）在应用程序
	// goroutine.
	sync.Mutex

	hardState pb.HardState
	snapshot  pb.Snapshot
	// ents[i]has raft log position i+snapshot.Metadata.Index 
	ents []pb.Entry
}

// NewMemoryStorage创建一个空的MemoryStorage.
func NewMemoryStorage() *MemoryStorage {
	return &MemoryStorage{
		// 从头开始时，用一个伪条目填充列表中的零项。
		ents: make([]pb.Entry, 1),
	}
}

// InitialState实现存储接口。
func (ms *MemoryStorage) InitialState() (pb.HardState, pb.ConfState, error) {
	return ms.hardState, ms.snapshot.Metadata.ConfState, nil
}

// SetHardState保存当前的硬状态。
func (ms *MemoryStorage) SetHardState(st pb.HardState) error {
	ms.Lock()
	defer ms.Unlock()
	ms.hardState = st
	return nil
}

// 查询指定范围的Entry
func (ms *MemoryStorage) Entries(lo, hi, maxSize uint64) ([]pb.Entry, error) {
	ms.Lock()
	defer ms.Unlock()
	offset := ms.ents[0].Index
	// 如采待查询的最小Indexf直（参数lo）小于FirstIndex，如l直接抛出异常
	if lo <= offset {
		return nil, ErrCompacted
	}
	// 如采待查询的最大Index值（参数hi）大于LastIndex，则直接抛出异常
	if hi > ms.lastIndex()+1 {
		getLogger().Panicf("entries' hi(%d) is out of bound lastindex(%d)", hi, ms.lastIndex())
	}
	// 如采MemoryStorage.ents只包含一条Entry，则其为空Entry，直接抛出异常
	if len(ms.ents) == 1 {
		return nil, ErrUnavailable
	}
	// 获取lo-hi之间的Entry，并返回
	ents := ms.ents[lo-offset : hi-offset]
	// 限制返回Entry切片的总字节大小
	return limitSize(ents, maxSize), nil
}

// 进行一系列边界检测，最终通过MemoryStorage.ents宇段读取指定Entry的Term值
func (ms *MemoryStorage) Term(i uint64) (uint64, error) {
	ms.Lock()
	defer ms.Unlock()
	offset := ms.ents[0].Index
	if i < offset {
		return 0, ErrCompacted
	}
	if int(i-offset) >= len(ms.ents) {
		return 0, ErrUnavailable
	}
	return ms.ents[i-offset].Term, nil
}

// LastIndex实现存储接口。
func (ms *MemoryStorage) LastIndex() (uint64, error) {
	ms.Lock()
	defer ms.Unlock()
	return ms.lastIndex(), nil
}

func (ms *MemoryStorage) lastIndex() uint64 {
	return ms.ents[0].Index + uint64(len(ms.ents)) - 1
}

// FirstIndex实现存储接口。
func (ms *MemoryStorage) FirstIndex() (uint64, error) {
	ms.Lock()
	defer ms.Unlock()
	return ms.firstIndex(), nil
}

func (ms *MemoryStorage) firstIndex() uint64 {
	return ms.ents[0].Index + 1
}

// 上层模块可以通过MemoryStorage.Snapshot（）方法获取SnapShot
// 该方法直接返回MemoryStorage.snapshot字段
func (ms *MemoryStorage) Snapshot() (pb.Snapshot, error) {
	ms.Lock()
	defer ms.Unlock()
	return ms.snapshot, nil
}

// 当MemoryStorage需要更新快照数据时
// 将Snapshot实例保存到MemoryStorage中
// 例如，在节点重启时，就会通过读取快照文件创建对应的SnapShot实例，然后保存到MemoryStorage中
func (ms *MemoryStorage) ApplySnapshot(snap pb.Snapshot) error {
	ms.Lock()	// 加锁同步，MemoryStorage实现了sync.Mutex
	defer ms.Unlock()	// ／方法结束后，释放锁

	// 通过快照的元数据比较当前MemoryStorage中记录的Snapshot与待处理的Snapshot数据的新旧程度
	msIndex := ms.snapshot.Metadata.Index
	snapIndex := snap.Metadata.Index
	if msIndex >= snapIndex {	// 比较两个pb.SnapShot所包含的最后一条记录的Index位
		return ErrSnapOutOfDate	// 如果待处理Snapshot数据比较旧，Ji!1J直接抛出异常
	}

	ms.snapshot = snap	// 更新MemoryStorage.snapshot字段
	// 重豆MemoryStorage.ents字段，此时在ents中只有一个空的Entry实例
	ms.ents = []pb.Entry{{Term: snap.Metadata.Term, Index: snap.Metadata.Index}}
	return nil
}

// 定期创建快照来记录当前节点的状态并压缩MemoryStorage.ents数组的空间降低内存使用
// CreateSnapshot（）方法，它会接收当前集群状态，以及SnapShot相关数据来更新snapshot字段，
// CreateSnapshot生成一个可以使用snapshot（）检索的快照而
// 可用于重构该点的状态。
// 如果自上次压缩后进行了任何配置更改，则必须传入上次ApplyConfChange的结果。
// 简单说明该方法的参数：
// i是新建Snapshot包含的最大的索引值，cs是当前集群的状态，data是新建Snapshot的具体数据
func (ms *MemoryStorage) CreateSnapshot(i uint64, cs *pb.ConfState, data []byte) (pb.Snapshot, error) {
	ms.Lock()
	defer ms.Unlock()
	// 边界检查，i必须大于当前Snapshot包含的最大Index值
	// 并且小于MemoryStorage的LastIndex佳，否则抛出异常（
	if i <= ms.snapshot.Metadata.Index {
		return pb.Snapshot{}, ErrSnapOutOfDate
	}

	offset := ms.ents[0].Index
	if i > ms.lastIndex() {
		getLogger().Panicf("snapshot %d is out of bound lastindex(%d)", i, ms.lastIndex())
	}
	// 更新MemoryStorage.snapshot的元数据
	ms.snapshot.Metadata.Index = i
	ms.snapshot.Metadata.Term = ms.ents[i-offset].Term
	if cs != nil {
		ms.snapshot.Metadata.ConfState = *cs
	}
	// 更新具体的快照数据
	ms.snapshot.Data = data
	return ms.snapshot, nil
}

// 将MemoryStorage.ents中指定索引之前的Entry记录全部抛弃，从而实现压缩MemoryStorage.ents的目的，
func (ms *MemoryStorage) Compact(compactIndex uint64) error {
	ms.Lock()
	defer ms.Unlock()
	offset := ms.ents[0].Index
	// 边界检测，firstlndex< compactlndex < lastlndex
	if compactIndex <= offset {
		return ErrCompacted
	}
	if compactIndex > ms.lastIndex() {
		getLogger().Panicf("compact %d is out of bound lastindex(%d)", compactIndex, ms.lastIndex())
	}
	// compactlndex对应Entry的下标
	i := compactIndex - offset
	// 创建新的切片，用来存储compactIndex之后的Entry
	ents := make([]pb.Entry, 1, 1+uint64(len(ms.ents))-i)
	ents[0].Index = ms.ents[i].Index
	ents[0].Term = ms.ents[i].Term
	// 将compactlndex之后的Entry拷贝到ents中，并更新MemoryStorage.ents字段
	ents = append(ents, ms.ents[i+1:]...)
	ms.ents = ents
	return nil
}

// 设置完快照数据之后，就可以MemoryStorage中追加Entry记录了
func (ms *MemoryStorage) Append(entries []pb.Entry) error {
	// 检测entries切片的长度
	if len(entries) == 0 {
		return nil
	}

	ms.Lock()
	defer ms.Unlock()

	first := ms.firstIndex()	// 获取当前MemoryStorage的Firstindex值
	// 获取待添加的最后一条Entry的Indexf直
	last := entries[0].Index + uint64(len(entries)) - 1

	// entries切片中所有的Entry都已经过时，无须添加任何Entry
	if last < first {
		return nil
	}
	// first之前的Entry已经记入Snapshot中，不应该再记录到ents中，所以将这部分Entry截拌
	if first > entries[0].Index {
		entries = entries[first-entries[0].Index:]
	}

	// 计算entryes切片中第一条可用的Entry与f工rst之间的差距
	offset := entries[0].Index - ms.ents[0].Index
	switch {
	case uint64(len(ms.ents)) > offset:
		// 保留MemoryStorage.ents中first～offset的部分，offset之后的部分被抛弃
		ms.ents = append([]pb.Entry{}, ms.ents[:offset]...)
		// 然后将待追加的Entry追加到MemoryStorage.ents中
		ms.ents = append(ms.ents, entries...)
	case uint64(len(ms.ents)) == offset:
		// 直接将待追加的日志记录（entries）追加到MemoryStorage中
		ms.ents = append(ms.ents, entries...)
	default:
		getLogger().Panicf("missing log entry [last: %d, append at: %d]",
			ms.lastIndex(), entries[0].Index)
	}
	return nil
}
